package com.shuang.tree46;

public class ConvertBST {

    //定义一个全局变量 用于记录当前节点的前一个节点的值
    int pre;

    public TreeNode convertBST(TreeNode root) {
        pre = 0;
        convertBST1(root);
        return root;
    }

    // 按右中左顺序遍历，累加即可
    public void convertBST1(TreeNode root) {
        //终止条件
        if (root == null) {
            return;
        }

        convertBST1(root.right);

        root.val += pre;

        //加完 移到当前节点位置的值 供下次使用
        pre = root.val;

        convertBST1(root.left);
    }
}
